package notInLeetcode;

/**
 * 圆环上有n(10)个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走k步回到0点共有多少种走法。
 * <p>
 * 输入: 2
 * 输出: 2
 * 解释：有2种方案。分别是0->1->0和0->9->0
 */
public class Dp1 {
    /**
     * @Description:
     * @Param: [k 点数, n 步数]
     * @return: int
     */
    public int sum(int n, int k) {
        if (n == 1 && k == 0) return 0;
        //dp[i][j]代表从0走i步到j的走法
        int[][] dp = new int[k + 1][n];
        dp[0][0] = 1;
        //从0走0步，到不了1 - n
        for (int i = 1; i < n; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i < k + 1; i++) {
            for (int j = 0; j < n; j++) {
                //0走i-1步到1的走法+走i-1步到9的走法
                dp[i][j] = dp[i - 1][(j - 1 + n) % n] + dp[i - 1][(j + 1) % n];
            }
        }
        return dp[k][0];
    }

    public static void main(String[] args) {
        Dp1 dp1 = new Dp1();
        int sum = dp1.sum(10, 5);
        System.out.println(sum);
    }
}
